One of the greatest modern enhancements to electronic processing and computing has been distribution of processing, storage, and like resources across remote distances and disparate devices. Access to data, applications, processes, databases, and the like has grown commensurate with an expansion of distributed networks. The success of transmission control protocol/Internet protocol (TCP/IP) electronic communication utilized with large networks, such as the Internet, has been an important contributor to enabling such distribution. In addition, the development of algorithms that can distribute resources of multiple servers amongst multiple clients has also aided the advancement and application of such distributed networks. As a result of such advancements, shared computing has become a viable and powerful tool in modern computing.
As with most automated computer processes, the introduction of shared computing has also fostered a desire to optimize such process. Load balancing of various assigned tasks amongst distributed machines and/or processes is one such example. Load balancing can be roughly characterized as an attempt at minimizing resources required to complete a certain number of tasks on a finite number of distributed machines. In some examples, the machines are able to inter-communicate with each other to best determine a mechanism with which to share and optimize resources; other examples restrict the machines to only that information that is locally available. Such restricted mechanisms can be termed non-cooperative or independent processes.
An example of a non-cooperative process can include a system having multiple distributed machines on a wired or wireless network, assigned a set of tasks. Load balancing desires to assign tasks to the distributed machines in such a manner as to minimize the completion time of all tasks. One method of achieving such goal is to design local scheduling policies that result in the desired load balancing. An advantage of local policies, e.g., policies enforced utilizing information local to a process, occurs in minimizing communication overload among distributed portions of a system. In many distributed systems, there are rational agents independently responsible for tasks of the set of tasks, who are selfishly motivated. In other words, each agent can schedule tasks independently to minimize their own completion time. In the context of such a system, one goal has been to develop local scheduling policies that motivate these individual agents to act both selfishly and in a manner that minimizes the completion time of the entire set of tasks. A solution is desirable if it can partially minimize communication amongst various machines and processes while only marginally increasing the completion time of the set of tasks when compared with cooperative systems.